{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Read N Characters Given read4 II - Call Multiple Times"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #interactive #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #交互 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: read"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #用 Read4 读取 N 个字符 II - 多次调用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个文件<meta charset=\"UTF-8\" />&nbsp;<code>file</code>&nbsp;，并且该文件只能通过给定的&nbsp;<code>read4</code>&nbsp;方法来读取，请实现一个方法使其能够使&nbsp;<code>read</code> 读取 <code>n</code> 个字符。<strong>注意：你的</strong>&nbsp;<strong><code>read</code> 方法可能会被调用多次。</strong></p>\n",
    "\n",
    "<p><strong>read4 的定义：</strong></p>\n",
    "\n",
    "<p><code>read4</code> API 从文件中读取<strong> 4 个连续的字符</strong>，然后将这些字符写入缓冲区数组 <code>buf4</code> 。</p>\n",
    "\n",
    "<p>返回值是读取的实际字符数。</p>\n",
    "\n",
    "<p>请注意，<code>read4()</code> 有其自己的文件指针，类似于 C 中的 <code>FILE * fp</code> 。</p>\n",
    "\n",
    "<pre>\n",
    "    参数类型: char[] buf4\n",
    "    返回类型: int\n",
    "\n",
    "注意: buf4[] 是目标缓存区不是源缓存区，read4 的返回结果将会复制到 buf4[] 当中。\n",
    "</pre>\n",
    "\n",
    "<p>下列是一些使用 <code>read4</code> 的例子：</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/07/01/157_example.png\" style=\"height: 403px; width: 600px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<code>File file(\"abcde\"); // 文件名为 \"abcde\"， 初始文件指针 (fp) 指向 'a' \n",
    "char[] buf4 = new char[4]; // 创建一个缓存区使其能容纳足够的字符\n",
    "read4(buf4); // read4 返回 4。现在 buf4 = \"abcd\"，fp 指向 'e'\n",
    "read4(buf4); // read4 返回 1。现在 buf4 = \"e\"，fp 指向文件末尾\n",
    "read4(buf4); // read4 返回 0。现在 buf4 = \"\"，fp 指向文件末尾</code></pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>read 方法：</strong></p>\n",
    "\n",
    "<p>通过使用 <code>read4</code> 方法，实现&nbsp;<code>read</code> 方法。该方法可以从文件中读取 <code>n</code> 个字符并将其存储到缓存数组&nbsp;<code>buf</code> 中。您&nbsp;<strong>不能&nbsp;</strong>直接操作&nbsp;<code>file</code> 。</p>\n",
    "\n",
    "<p>返回值为实际读取的字符。</p>\n",
    "\n",
    "<p><strong>read&nbsp;的定义：</strong></p>\n",
    "\n",
    "<pre>\n",
    "    参数类型:  char[] buf, int n\n",
    "    返回类型:  int\n",
    "\n",
    "注意: buf[] 是目标缓存区不是源缓存区，你需要将结果写入 buf[] 中。\n",
    "</pre>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你 <strong>不能</strong> 直接操作该文件，文件只能通过 <code>read4</code> 获取而 <strong>不能</strong> 通过 <code>read</code>。</li>\n",
    "\t<li><code>read</code>&nbsp; 函数可以被调用&nbsp;<strong>多次</strong>。</li>\n",
    "\t<li>请记得&nbsp;<strong>重置&nbsp;</strong>在 Solution 中声明的类变量（静态变量），因为类变量会&nbsp;<strong>在多个测试用例中保持不变</strong>，影响判题准确。请 <a href=\"https://support.leetcode-cn.com/hc/kb/section/1071534/\" target=\"_blank\">查阅</a> 这里。</li>\n",
    "\t<li>你可以假定目标缓存数组&nbsp;<code>buf</code> 保证有足够的空间存下 n 个字符。&nbsp;</li>\n",
    "\t<li>保证在一个给定测试用例中，<code>read</code> 函数使用的是同一个 <code>buf</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> file = \"abc\"， queries = [1,2,1]\n",
    "<strong>输出：</strong>[1,2,0]\n",
    "<strong>解释：</strong>测试用例表示以下场景:\n",
    "File file(\"abc\");\n",
    "Solution sol;\n",
    "sol.read (buf, 1); // 调用 read 方法后，buf 应该包含 “a”。我们从文件中总共读取了 1 个字符，所以返回 1。\n",
    "sol.read (buf, 2); // 现在 buf 应该包含 \"bc\"。我们从文件中总共读取了 2 个字符，所以返回 2。\n",
    "sol.read (buf, 1); // 我们已经到达文件的末尾，不能读取更多的字符。所以返回 0。\n",
    "假设已经分配了 buf ，并保证有足够的空间存储文件中的所有字符。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>file = \"abc\"， queries = [4,1]\n",
    "<strong>输出：</strong>[3,0]\n",
    "<strong>解释：</strong>测试用例表示以下场景:\n",
    "File file(\"abc\");\n",
    "Solution sol;\n",
    "sol.read (buf, 4); // 调用 read 方法后，buf 应该包含 “abc”。我们从文件中总共读取了 3 个字符，所以返回 3。\n",
    "sol.read (buf, 1); // 我们已经到达文件的末尾，不能读取更多的字符。所以返回 0。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= file.length &lt;= 500</code></li>\n",
    "\t<li><code>file</code>&nbsp;由英语字母和数字组成</li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= queries[i] &lt;= 500</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [read-n-characters-given-read4-ii-call-multiple-times](https://leetcode.cn/problems/read-n-characters-given-read4-ii-call-multiple-times/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [read-n-characters-given-read4-ii-call-multiple-times](https://leetcode.cn/problems/read-n-characters-given-read4-ii-call-multiple-times/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n[1,2,1]', '\"abc\"\\n[4,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alienOrder(self, words: List[str]) -> str:\n",
    "        # 构建字符集\n",
    "        n_words = len(words)\n",
    "        postorder = defaultdict(list)\n",
    "        \n",
    "        for i in range(n_words-1):\n",
    "            a = words[i]\n",
    "            b = words[i+1]\n",
    "            len_max = max(len(a), len(b))\n",
    "            for j in range(len_max):\n",
    "                if j ==  len(b): # a长\n",
    "                    return \"\"\n",
    "                elif j == len(a):# b长\n",
    "                    break # 下一组\n",
    "                elif a[j] != b[j]:\n",
    "                    postorder[a[j]].append(b[j])\n",
    "                    break\n",
    "        vis = [False] * 26\n",
    "        on_path = [False] * 26 \n",
    "        path = []\n",
    "        has_cycle = False \n",
    "        def dfs(graph, c):\n",
    "            idx = ord(c) - ord('a')\n",
    "            nonlocal has_cycle\n",
    "            \n",
    "            if on_path[idx]:\n",
    "                has_cycle = True\n",
    "            if has_cycle or vis[idx]:\n",
    "                return \n",
    "            on_path[idx] = True \n",
    "            vis[idx] = True\n",
    "            for nxt_c in postorder[c]:\n",
    "                dfs(graph, nxt_c)\n",
    "            path.append(c)\n",
    "            on_path[idx] = False \n",
    "        char_set = set()\n",
    "        for i in range(n_words):\n",
    "            for c in words[i]:\n",
    "                char_set.add(c)\n",
    "        keyset = set( postorder.keys())\n",
    "        for c in keyset:\n",
    "            dfs(postorder,c)\n",
    "\n",
    "        if has_cycle:\n",
    "            return \"\"\n",
    "        path_already = set(path)\n",
    "        for  c in char_set:\n",
    "            if c not in path_already:\n",
    "                path.append(c)\n",
    "        return \"\".join(path[::-1])\n",
    "\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        adjList, res = [set() for _ in range(n)], [[] for _ in range(n)]\n",
    "        for x in edges:\n",
    "            adjList[x[0]].add(x[1])\n",
    "        for i in range(n):\n",
    "            already = adjList[i]\n",
    "            stack = list(adjList[i])\n",
    "            while stack:\n",
    "                pres = stack.pop()\n",
    "                res[pres].append(i)\n",
    "                for x in adjList[pres]:\n",
    "                    if x not in already:\n",
    "                        already.add(x)\n",
    "                        stack.append(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def avoidFlood(self, rains: List[int]) -> List[int]:\n",
    "        dic, heap, res, already = {}, [], [], set()\n",
    "        for i in range(len(rains)):\n",
    "            if rains[i]:\n",
    "                dic.setdefault(rains[i], []).append(i)\n",
    "        for x in dic:\n",
    "            dic[x].append(float(\"inf\"))\n",
    "            dic[x].reverse()\n",
    "        for x in rains:\n",
    "            if x:\n",
    "                if x in already:\n",
    "                    return []\n",
    "                already.add(x)\n",
    "                dic[x].pop()\n",
    "                heappush(heap, [dic[x].pop(), x])\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                if heap:\n",
    "                    pres = heappop(heap)\n",
    "                    dic[pres[1]].append(pres[0])\n",
    "                    already.remove(pres[1])\n",
    "                    res.append(pres[1])\n",
    "                else:\n",
    "                    res.append(1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def balanceBST(self, root: TreeNode) -> TreeNode:\n",
    "        nums = []\n",
    "        def traversal(cur):\n",
    "            if not cur:    return\n",
    "            traversal(cur.left)\n",
    "            nums.append(cur.val)\n",
    "            traversal(cur.right)\n",
    "\n",
    "        def creadBST(nums, l, r):\n",
    "            if l > r:   return\n",
    "            mid = (l+r) // 2\n",
    "            root = TreeNode(nums[mid])\n",
    "            root.left = creadBST(nums, l, mid-1)\n",
    "            root.right = creadBST(nums, mid+1, r)\n",
    "            return root\n",
    "        \n",
    "        traversal(root)\n",
    "        return creadBST(nums, 0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode-cn.com/problems/implement-queue-using-stacks/\n",
    "from threading import Lock\n",
    "\n",
    "from functools import wraps\n",
    "\n",
    "\n",
    "class Stack:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.stack = []\n",
    "\n",
    "    def push(self, ele):\n",
    "        self.stack.append(ele)\n",
    "\n",
    "    def pop(self):\n",
    "        return self.stack.pop(-1)\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.stack)\n",
    "\n",
    "    def top(self):\n",
    "        return self.stack[-1]\n",
    "\n",
    "    def empty(self):\n",
    "        return True if self.size() == 0 else False\n",
    "\n",
    "\n",
    "def output_pre_check(func):\n",
    "    @wraps(func)\n",
    "    def wrapper(self, *args, **kwargs):\n",
    "        self._output_pre_check()\n",
    "        res = func(self, *args, **kwargs)\n",
    "        return res\n",
    "    return wrapper\n",
    "\n",
    "\n",
    "class MyQueue:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self._input_stack = Stack()\n",
    "        self._output_stack = Stack()\n",
    "        self._lock = Lock()\n",
    "\n",
    "    def push(self, x: int) -> None:\n",
    "        \"\"\"\n",
    "        Push element x to the back of queue.\n",
    "        \"\"\"\n",
    "        self._input_stack.push(x)\n",
    "\n",
    "    @output_pre_check\n",
    "    def pop(self) -> int:\n",
    "        \"\"\"\n",
    "        Removes the element from in front of queue and returns that element.\n",
    "        \"\"\"\n",
    "        res = self._output_stack.pop()\n",
    "        return res\n",
    "\n",
    "    def _transfer_ele_from_input_to_output(self):\n",
    "        with self._lock:\n",
    "            while not self._input_stack.empty():\n",
    "                self._output_stack.push(self._input_stack.pop())\n",
    "\n",
    "    def _output_pre_check(self):\n",
    "        if self._output_stack.empty():\n",
    "            self._transfer_ele_from_input_to_output()\n",
    "\n",
    "    @output_pre_check\n",
    "    def peek(self) -> int:\n",
    "        \"\"\"\n",
    "        Get the front element.\n",
    "        \"\"\"\n",
    "        # self._transfer_ele_from_input_to_output()\n",
    "        return self._output_stack.top()\n",
    "\n",
    "    def empty(self) -> bool:\n",
    "        \"\"\"\n",
    "        Returns whether the queue is empty.\n",
    "        \"\"\"\n",
    "        return True if self.size() == 0 else False\n",
    "\n",
    "    def size(self):\n",
    "        return self._output_stack.size() + self._input_stack.size()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums = []\n",
    "        for _ in range(10):\n",
    "            nums.append(rand7())\n",
    "\n",
    "        import math\n",
    "        return sum(nums)%10+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    mem_map = {}\n",
    "    idx = 0\n",
    "    for i in range(1, 8):\n",
    "        for j in range(1, 8):\n",
    "            if idx >= 40:\n",
    "                break\n",
    "            mem_map[(i, j)] = idx % 10 + 1\n",
    "            idx += 1\n",
    "\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            l, r = rand7(), rand7()\n",
    "            print(l, r)\n",
    "            if (l, r) in self.mem_map:\n",
    "                return self.mem_map[(l, r)]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "def rand01():\n",
    "    res = rand7()\n",
    "    while res == 7:\n",
    "        res = rand7()\n",
    "    if res >= 4:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        one = rand01()\n",
    "        two = rand01()\n",
    "        three = rand01()\n",
    "        four = rand01()\n",
    "        print(four , one, two, three)\n",
    "        res = (four << 3) + (one << 2) + (two << 1) + three \n",
    "        print(res)\n",
    "        while res < 1 or res > 10:\n",
    "            one = rand01()\n",
    "            two = rand01()\n",
    "            three = rand01()\n",
    "            four = rand01()\n",
    "            print(four , one, two, three)\n",
    "            res = (four << 3) + (one << 2) + (two << 1) + three \n",
    "            print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = 7*(rand7()-1)+rand7()\n",
    "        while n>40:\n",
    "            n = 7*(rand7()-1)+rand7()\n",
    "        return math.ceil(n/4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = 7*(rand7()-1)+rand7()\n",
    "        while n>40:\n",
    "            n = 7*(rand7()-1)+rand7()\n",
    "        return math.ceil(n/4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        idx = 41\n",
    "        while idx > 40:\n",
    "            i, j = rand7(), rand7()\n",
    "            idx = (j - 1) * 7 + i\n",
    "        if idx % 10 == 0:\n",
    "            return 10\n",
    "        return idx % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        first = rand7()\n",
    "        second = rand7()\n",
    "        while first > 6:\n",
    "            first = rand7()\n",
    "        while second > 5:\n",
    "            second = rand7()\n",
    "\n",
    "        return second if first&1 else second + 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        total = 0\n",
    "        for i in range(10):\n",
    "            total += rand7()\n",
    "        return total%10 if total%10 != 0 else 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            num = (rand7() - 1) * 7 + rand7()  # 生成 [1,49] 范围内的均匀随机数\n",
    "            if num <= 10:\n",
    "                return num "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = (rand7()-1) * 7 + rand7()\n",
    "\n",
    "        while res > 40:\n",
    "            res = (rand7()-1) * 7 + rand7()\n",
    "        \n",
    "        return res % 10 + 1 \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            idx = (rand7() - 1) * 7 + rand7()\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            res = rand7() * 7 + rand7() - 8\n",
    "            if res < 40:\n",
    "                return res % 10 + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        while True:    \n",
    "            a = rand7()\n",
    "            b = rand7()\n",
    "\n",
    "            # 注意rand7是得到1-7的数字，要形成1-49的数字，需要a - 1\n",
    "            c = (a  - 1)* 7 + b\n",
    "\n",
    "            if c <= 40:\n",
    "                # 使得前4个数都是1，那么需要c - 1变成0-3\n",
    "                #return (c- 1)//4 + 1\n",
    "                return (c - 1) % 10 + 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            num=(rand7()-1)*7+rand7()\n",
    "            if num<=40:\n",
    "                return (num-1)%10+1\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #a =  #1-49\n",
    "        a = (rand7()-1)*7 + rand7()\n",
    "        while a>40:\n",
    "            a = (rand7()-1)*7 + rand7()   \n",
    "        return 1+(a-1)%10 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        r1 = r2 = True\n",
    "        s1 = s2 = 0\n",
    "        while r1:\n",
    "            s1 = rand7()\n",
    "            if s1 <= 5:\n",
    "                r1 = False\n",
    "        while r2:\n",
    "            s2 = rand7()\n",
    "            if s2 <= 2:\n",
    "                r2 = False\n",
    "                if s2 == 1:\n",
    "                    s2 = 0\n",
    "                elif s2 == 2:\n",
    "                    s2 = 5\n",
    "        return s1 + s2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x = 11\n",
    "        while x > 10:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            x = (row - 1) * 7 + col\n",
    "        \n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 10ci\n",
    "        while True:\n",
    "            # print(1)\n",
    "            a = rand7()\n",
    "            b = rand7()\n",
    "            if b == 1:\n",
    "                return a\n",
    "            elif b == 2:\n",
    "                if a < 4:\n",
    "                    return 7 + a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 加0,1,2,3\n",
    "        num = (rand7()-1)*7+rand7()\n",
    "        while num > 40:\n",
    "            num =  (rand7()-1)*7+rand7()\n",
    "        \n",
    "        return num % 10 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 加0,1,2,3\n",
    "        while True:\n",
    "            num = (rand7()-1)*7+rand7()\n",
    "            if num <= 40 :\n",
    "                return num % 10 + 1          \n",
    "            num = (num - 40 - 1)*7+rand7()\n",
    "            if num <= 60 :\n",
    "                return num % 10 + 1\n",
    "            num = (num -60 - 1)*7+rand7()\n",
    "            if num <= 20 :\n",
    "                return num %10 +1\n",
    "       \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row-1)*7+col\n",
    "            if idx<=40:\n",
    "                return 1+(idx-1)%10\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            row=rand7()\n",
    "            col=rand7()\n",
    "            idx=(row-1)*7+col\n",
    "            if idx<=40:\n",
    "                return (idx-1)%10+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        while not 1 <= res <= 10:\n",
    "            res = (rand7() - 1) * 7 + rand7()\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row - 1) * 7 + col\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return randint(1, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            index = (rand7()-1) * 7 + rand7()\n",
    "            if index <= 40:\n",
    "                return (index-1) % 10 + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            x = rand7()\n",
    "            y = rand7()\n",
    "            s = (x-1)*7 + y\n",
    "            if s <= 40:\n",
    "                return 1 + s % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        num = (rand7() - 1) * 7 + rand7() # 取得0-48之间的数字\n",
    "        # 如数字>39 （40-48），舍弃，重新选取\n",
    "        while num > 40:\n",
    "            num =  (rand7() - 1) * 7 + rand7()  \n",
    "        # 如数字在0-39之间，模10加一，恰好可以等概率取得1-10之间的十个数字\n",
    "        return num % 10 + 1    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x = (rand7() - 1) * 7 + rand7() - 1\n",
    "        return self.rand10() if x >= 40 else x % 10 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "# class Solution:\n",
    "#     def rand10(self):\n",
    "#         \"\"\"\n",
    "#         :rtype: int\n",
    "#         \"\"\"\n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row - 1) * 7 + col\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n",
    "            \n",
    "            \n",
    "# class Solution:\n",
    "#     def rand10(self) -> int:\n",
    "#         while True:\n",
    "#             a = rand7()\n",
    "#             b = rand7()\n",
    "#             idx = (a - 1) * 7 + b\n",
    "#             if idx <= 40:\n",
    "#                 return 1 + (idx - 1) % 10\n",
    "#             a = idx - 40\n",
    "#             b = rand7()\n",
    "#             # get uniform dist from 1 - 63\n",
    "#             idx = (a - 1) * 7 + b\n",
    "#             if idx <= 60:\n",
    "#                 return 1 + (idx - 1) % 10\n",
    "#             a = idx - 60\n",
    "#             b = rand7()\n",
    "#             # get uniform dist from 1 - 21\n",
    "#             idx = (a - 1) * 7 + b\n",
    "#             if idx <= 20:\n",
    "#                 return 1 + (idx - 1) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            r, c = rand7(), rand7()\n",
    "            idx = (r - 1) * 7 + c\n",
    "            if idx <= 40:\n",
    "                return (idx - 1) % 10 + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        '''\n",
    "        先生成一个7*7的矩阵，拒绝多余的9个\n",
    "        '''\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            index = (row - 1) * 7 + col\n",
    "            if index <= 40:\n",
    "                return (index-1) % 10 + 1\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        tab = {2 : 1,3 : 2,5 : 3,7 : 4,8 : 5,10 : 6,14 : 7,15 : 8,20 : 9,21 : 10}\n",
    "        n = 0\n",
    "        while n not in tab:\n",
    "            n = rand7() * rand7()\n",
    "        return tab[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            # 1)生成rand49()\n",
    "            index=(rand7()-1)*7+rand7()\n",
    "            if (index<=10):\n",
    "                return index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            a = rand7()\n",
    "            b = rand7()\n",
    "            n = (a - 1) * 7 + b\n",
    "            if n <= 40: return n % 10 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ret=11\n",
    "        while ret>10:\n",
    "            ret=1\n",
    "            for i in range(4):\n",
    "                temp=rand7()\n",
    "                while temp==4:temp=rand7()\n",
    "                if temp>4:ret+=2**i\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row - 1) * 7 + col\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            r0 = rand7()\n",
    "            r1 = rand7()\n",
    "            v = r0 + (r1 - 1) * 7\n",
    "            if v > 40:\n",
    "                r0 = v % 40  # 1-9\n",
    "                r1 = rand7() # 1-7\n",
    "                v = r0 + (r1 - 1) * 7 # 1-63\n",
    "                if v > 60:\n",
    "                    r0 = v % 60 # 1 2 3\n",
    "                    r1 = rand7() # 1-7\n",
    "                    v = r0 + (r1 - 1) * 7 # 21\n",
    "                    if v > 20:\n",
    "                        continue\n",
    "                    else:\n",
    "                        return 1 + (v - 1) % 10\n",
    "                else:\n",
    "                    return 1 + (v - 1) % 10\n",
    "            return 1 + (v - 1) % 10\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x = 11\n",
    "        while x > 10:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            x = (row - 1) * 7 + col\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            num = rand7() + (rand7() - 1) * 7\n",
    "            if num <= 40:\n",
    "                return 1 + (num - 1) % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "class Solution:\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row - 1) * 7 + col\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n",
    "\n",
    "\n",
    "# 1/7\n",
    "# 选两次, 就有如下结果:\n",
    "\n",
    "# 1 2 3 4 5 6 7\n",
    "# 1 2 3 4 5 6 7\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a,b = 0, 0\n",
    "        while True:\n",
    "            a=rand7()\n",
    "            if a<7:\n",
    "                break \n",
    "        while True:\n",
    "            b=rand7()\n",
    "            if b<6:\n",
    "                break   \n",
    "        return b if a%2==0 else b+5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            num = (rand7() - 1) * 7 + rand7()\n",
    "            if not 1 <= num <= 10:\n",
    "                continue\n",
    "            return num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            #r = (rand7() - 1) * 7 + rand7()\n",
    "            #if r <= 40: return r % 10 + 1\n",
    "            r = rand7() * 7 - rand7()\n",
    "            if r < 40: return r % 10 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num1=rand7()\n",
    "        num2=rand7()\n",
    "        num=num1*10+num2\n",
    "        #依据num生成答案\n",
    "        #num是一个8进制数，它的第0，1位是【1，7】中的随机数\n",
    "        #转换为十进制数四十九种可能，我们取其中10种\n",
    "        while num>=66:\n",
    "            num1=rand7()\n",
    "            num2=rand7()\n",
    "            num=num1*10+num2\n",
    "        \n",
    "        if num<=14:return 1\n",
    "        elif num<=21:return 2\n",
    "        elif num<=25:return 3\n",
    "        elif num<=32:return 4\n",
    "        elif num<=36:return 5\n",
    "        elif num<=43:return 6\n",
    "        elif num<=47:return 7\n",
    "        elif num<=54:return 8\n",
    "        elif num<=61:return 9\n",
    "        elif num<=65:return 10\n",
    "        return 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import random\n",
    "class RandomizedCollection:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.l = []\n",
    "        \n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        x = True\n",
    "        if val in self.l:\n",
    "            x = False\n",
    "        self.l.append(val)\n",
    "        return x\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the collection. Returns true if the collection contained the specified element.\n",
    "        \"\"\"\n",
    "        if val not in self.l:\n",
    "            return False\n",
    "        else:\n",
    "            self.l.remove(val)\n",
    "            return True\n",
    "\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the collection.\n",
    "        \"\"\"\n",
    "        x = random.randint(0, len(self.l) - 1)\n",
    "        return self.l[x]\n",
    "\n",
    "\n",
    "# Your RandomizedCollection object will be instantiated and called as such:\n",
    "# obj = RandomizedCollection()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class RandomizedCollection:\n",
    "\n",
    "#     def __init__(self):\n",
    "#         self.array = []\n",
    "#         self.map = dict()\n",
    "#         self.size = 0\n",
    "\n",
    "\n",
    "#     def insert(self, val: int) -> bool:\n",
    "#         if val in self.map.keys():\n",
    "#             self.map[val].append(self.size)\n",
    "#             self.size += 1\n",
    "#             self.array.append(val)\n",
    "#             return False\n",
    "#         else:\n",
    "#             self.map[val]=[self.size]\n",
    "#             self.size += 1\n",
    "#             self.array.append(val)\n",
    "#             return True\n",
    "\n",
    "\n",
    "#     def remove(self, val: int) -> bool:\n",
    "#         if val in self.map.keys():\n",
    "#             temp = self.map[val].pop(0)\n",
    "#             temp_num = self.array[self.size-1]\n",
    "#             self.array[temp] = temp_num\n",
    "#             if self.map[temp_num]:\n",
    "#                 self.map[temp_num].pop(0)\n",
    "#             self.map[temp_num].append(temp)\n",
    "#             self.size -= 1\n",
    "#             return True\n",
    "#         else:\n",
    "#             return False\n",
    "\n",
    "\n",
    "\n",
    "#     def getRandom(self) -> int:\n",
    "#         return choice(self.array)\n",
    "\n",
    "class RandomizedCollection:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.l = []\n",
    "        \n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        x = True\n",
    "        if val in self.l:\n",
    "            x = False\n",
    "        self.l.append(val)\n",
    "        return x\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the collection. Returns true if the collection contained the specified element.\n",
    "        \"\"\"\n",
    "        if val not in self.l:\n",
    "            return False\n",
    "        else:\n",
    "            self.l.remove(val)\n",
    "            return True\n",
    "\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the collection.\n",
    "        \"\"\"\n",
    "        x = random.randint(0, len(self.l) - 1)\n",
    "        return self.l[x]\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedCollection object will be instantiated and called as such:\n",
    "# obj = RandomizedCollection()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedCollection object will be instantiated and called as such:\n",
    "# obj = RandomizedCollection()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedCollection:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.nums=[]\n",
    "        self.size=0\n",
    "        self.index=defaultdict(set)\n",
    "        \n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        not_exist=len(self.index[val])==0\n",
    "        self.index[val].add(len(self.nums))\n",
    "        self.nums.append(val)\n",
    "        self.size+=1\n",
    "        return not_exist\n",
    "\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the collection. Returns true if the collection contained the specified element.\n",
    "        \"\"\"\n",
    "        if len(self.index[val])!=0:\n",
    "            ind_val=self.index[val].pop()\n",
    "            # 这里注意一下分类讨论 如果弹出的是末尾元素 则不是置换 直接弹出即可\n",
    "            if ind_val!=self.size-1:\n",
    "                # 和最后一个元素置换\n",
    "                self.nums[ind_val], self.nums[self.size-1]=self.nums[self.size-1], self.nums[ind_val]\n",
    "                self.nums.pop()\n",
    "                #更新被置换的元素的id\n",
    "                swap_val, swap_id=self.nums[ind_val], self.size-1\n",
    "                self.index[swap_val].remove(swap_id)\n",
    "                self.index[swap_val].add(ind_val)\n",
    "                # 更新数组的实际大小\n",
    "                self.size-=1\n",
    "            else:\n",
    "                self.nums.pop()\n",
    "                self.size-=1\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the collection.\n",
    "        \"\"\"\n",
    "        i_select=random.randint(0, self.size-1)\n",
    "        return choice(self.nums)\n",
    "  \n",
    "\n",
    "\n",
    "# Your RandomizedCollection object will be instantiated and called as such:\n",
    "# obj = RandomizedCollection()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.dat, self.dicti = [], {}\n",
    "\n",
    "    def insert(self, val):\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        :type val: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if val in self.dicti:\n",
    "            return False\n",
    "        self.dicti[val] = len(self.dat)\n",
    "        self.dat.append(val)\n",
    "        return True\n",
    "\n",
    "    def remove(self, val):\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        :type val: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if val not in self.dicti:\n",
    "            return False\n",
    "        self.dicti[self.dat[-1]] = self.dicti[val]\n",
    "        self.dat[self.dicti[self.dat[-1]]] = self.dat[-1]\n",
    "        del self.dicti[val]\n",
    "        self.dat.pop()\n",
    "        return True\n",
    "\n",
    "    def getRandom(self):\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return random.choice(self.dat)\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "\n",
    "class RandomizedSet(object):\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.map = {}\n",
    "        self.content = []\n",
    "\n",
    "    def insert(self, val):\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        :type val: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        print(\"insert \" + str(val))\n",
    "        if not val in self.map:\n",
    "            self.content.append(val)\n",
    "            self.map[val] = len(self.content) - 1\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def remove(self, val):\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        :type val: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        print(val)\n",
    "        if val in self.map:\n",
    "            delTarPos = self.map[val]\n",
    "            lastPos = len(self.content) - 1\n",
    "            lastVal = self.content[-1]\n",
    "            self.content[lastPos], self.content[delTarPos] = self.content[delTarPos], self.content[lastPos]\n",
    "            self.map[val] = lastVal\n",
    "            self.map[lastVal] = delTarPos\n",
    "            self.content.pop()\n",
    "            self.map.pop(val, None)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def getRandom(self):\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(self.content) > 0:\n",
    "            return self.content[random.randint(0, len(self.content) - 1)]\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from random import choice\n",
    "class RandomizedSet():\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.dict = {}\n",
    "        self.list = []\n",
    "\n",
    "        \n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if val in self.dict:\n",
    "            return False\n",
    "        self.dict[val] = len(self.list)\n",
    "        self.list.append(val)\n",
    "        return True\n",
    "        \n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if val in self.dict:\n",
    "            # move the last element to the place idx of the element to delete\n",
    "            last_element, idx = self.list[-1], self.dict[val]\n",
    "            self.list[idx], self.dict[last_element] = last_element, idx\n",
    "            # delete the last element\n",
    "            self.list.pop()\n",
    "            del self.dict[val]\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        return choice(self.list)\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.stack = [] \n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if val not in self.stack:\n",
    "            self.stack.append(val)\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if val in self.stack:\n",
    "            self.stack.remove(val)\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        n = len(self.stack)\n",
    "        ran = random.randint(0, n-1)\n",
    "        return self.stack[ran]\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.memo = {}\n",
    "        self.nums = []\n",
    "\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if val not in self.memo:\n",
    "            self.memo[val] = len(self.nums)\n",
    "            self.nums.append(val)\n",
    "            return True \n",
    "        return False\n",
    "\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if val in self.memo:\n",
    "            idx = self.memo[val]\n",
    "            last_idx = len(self.nums) - 1\n",
    "            last_val = self.nums[last_idx]\n",
    "            self.nums[idx] = last_val\n",
    "            self.memo[last_val] = idx\n",
    "            self.nums.pop()\n",
    "            del self.memo[val]\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        return self.nums[random.randint(0, len(self.nums) - 1)]\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.s = []\n",
    "\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if val not in self.s:\n",
    "            self.s.append(val)\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if val in self.s:\n",
    "            self.s.remove(val)\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        import random\n",
    "        return random.choice(self.s)\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.ans_dict = {}\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if not self.ans_dict:\n",
    "            self.ans_dict[val] = 1\n",
    "            return True\n",
    "        if val in self.ans_dict.keys():\n",
    "            return False\n",
    "        else:\n",
    "            self.ans_dict[val] = 1\n",
    "            return True\n",
    "\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if val in self.ans_dict.keys():\n",
    "            del self.ans_dict[val]\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        key_list = list(self.ans_dict.keys())\n",
    "        key_len = len(key_list)\n",
    "        if key_len < 2:\n",
    "            if key_len: \n",
    "                return key_list[0] \n",
    "            else: return key_list\n",
    "        random_num = random.randint(1,key_len)\n",
    "        return key_list[random_num-1]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "val = 2\n",
    "obj = RandomizedSet()\n",
    "param_1 = obj.insert(val)\n",
    "param_2 = obj.remove(val)\n",
    "param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self._se = set()\n",
    "\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if val not in self._se:\n",
    "            self._se.add(val)\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if val not in self._se:\n",
    "            return False\n",
    "        else:\n",
    "            self._se.remove(val)\n",
    "            return True\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        return random.choice(list(self._se))\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.li=[] # 只存在unique的元素\n",
    "        self.dic={} \n",
    "\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        flag = val in self.li \n",
    "        if not flag: # 不存在\n",
    "            self.dic[val]={len(self.li),}\n",
    "            self.li.append(val)\n",
    "        # 存在啥也不做\n",
    "        return  not flag\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        flag = val in self.li \n",
    "        if flag: # 用最后一个数来替换要删除的数\n",
    "            last_idx=len(self.li)-1\n",
    "            v=self.li[last_idx]\n",
    "\n",
    "            index=self.dic[val].pop()\n",
    "\n",
    "            self.li[index]=self.li[last_idx]\n",
    "\n",
    "            if last_idx!=index:\n",
    "                self.dic[v].remove(last_idx)\n",
    "                self.dic[v].add(index)\n",
    "            \n",
    "            if not len(self.dic[val]):\n",
    "                self.dic.pop(val)\n",
    "            self.li.pop()\n",
    "            \n",
    "        return flag\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        return random.choice(self.li)\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.__hash=[-1]*(99991)\n",
    "        self.__list=[]\n",
    "        self.__M=99991\n",
    "        self.__B=233\n",
    "\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if self.__hash[(val*self.__B)%self.__M]==-1:\n",
    "            self.__hash[(val*self.__B)%self.__M]=len(self.__list)\n",
    "            self.__list.append(val)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        hash_index=(val*self.__B)%self.__M\n",
    "        if self.__hash[hash_index]!=-1:\n",
    "            t=self.__hash[hash_index]\n",
    "            self.__hash[hash_index]=-1\n",
    "            if len(self.__list)>1 and t<len(self.__list)-1:\n",
    "                self.__list[t]=self.__list[len(self.__list)-1]\n",
    "                self.__hash[(self.__list[t]*self.__B)%self.__M]=t\n",
    "            self.__list.pop()\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        if not self.__list:\n",
    "            return None\n",
    "        import random\n",
    "        t=int(random.random()*1000000)\n",
    "        index=t%len(self.__list)\n",
    "        return self.__list[index]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.data = [[] for _ in range(100000)]\n",
    "        self.size = 0\n",
    "        self.pos = []\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if len(self.data[val % 1000]) and val in self.data[val % 1000]:\n",
    "            return False\n",
    "        self.data[val % 1000].append(val)\n",
    "        self.size += 1\n",
    "        self.pos.append(val % 1000)\n",
    "        return True\n",
    "    \n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        arr = self.data[val % 1000]\n",
    "        if arr and val in arr:\n",
    "            arr.remove(val)\n",
    "            self.size -= 1\n",
    "            self.pos.remove(val % 1000)\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "\n",
    "        pos = random.choice(self.pos)\n",
    "        return random.choice(self.data[pos])\n",
    "        \n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.data = [[] for _ in range(100000)]\n",
    "        self.size = 0\n",
    "        self.pos = []\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if len(self.data[val % 1000]) and val in self.data[val % 1000]:\n",
    "            return False\n",
    "        self.data[val % 1000].append(val)\n",
    "        self.size += 1\n",
    "        self.pos.append(val % 1000)\n",
    "        return True\n",
    "    \n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        arr = self.data[val % 1000]\n",
    "        if arr and val in arr:\n",
    "            arr.remove(val)\n",
    "            self.size -= 1\n",
    "            self.pos.remove(val % 1000)\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "\n",
    "        pos = random.choice(self.pos)\n",
    "        return random.choice(self.data[pos])\n",
    "        \n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.set = set()\n",
    "\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if val in self.set:\n",
    "            return False\n",
    "        self.set.add(val)\n",
    "        return True\n",
    "\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if val in self.set:\n",
    "            self.set.remove(val)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        import numpy as np\n",
    "        idx = np.random.randint(0, len(self.set))\n",
    "        k = list(self.set)[idx]\n",
    "        return k\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.dic={}\n",
    "        self.lst=[]\n",
    "\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if not self.dic.get(val):\n",
    "            self.dic[val]=1\n",
    "            self.lst.append(val)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if self.dic.get(val):\n",
    "            self.dic[val]=0\n",
    "            self.lst.remove(val)\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        import numpy\n",
    "        x=numpy.random.randint(len(self.lst))\n",
    "        if len(self.lst)==0:\n",
    "            return False\n",
    "        return self.lst[x]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedSet:\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.sse = set()\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if val not in self.sse:\n",
    "            self.sse.add(val)\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if val in self.sse:\n",
    "            self.sse.remove(val)\n",
    "            return True \n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        import numpy as np\n",
    "        n = np.random.randint(0,len(self.sse))\n",
    "        return tuple(self.sse)[n]\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class RandomizedSet:\n",
    "    \n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        \n",
    "        self.a = {}\n",
    "        self.vec = []\n",
    "\n",
    "\n",
    "    def insert(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Inserts a value to the set. Returns true if the set did not already contain the specified element.\n",
    "        \"\"\"\n",
    "        if self.a.__contains__(val):\n",
    "            return False\n",
    "        self.a[val]= self.a.__len__()\n",
    "        self.vec.append(val)\n",
    "        return True\n",
    "\n",
    "    def remove(self, val: int) -> bool:\n",
    "        \"\"\"\n",
    "        Removes a value from the set. Returns true if the set contained the specified element.\n",
    "        \"\"\"\n",
    "        if not self.a.__contains__(val):\n",
    "            return False\n",
    "        b = self.a[val]\n",
    "        self.a[self.vec[-1]] = b\n",
    "        self.vec[b], self.vec[-1] = self.vec[-1], self.vec[b]\n",
    "        self.vec.pop()\n",
    "        self.a.pop(val)\n",
    "        return True\n",
    "\n",
    "    def getRandom(self) -> int:\n",
    "        \"\"\"\n",
    "        Get a random element from the set.\n",
    "        \"\"\"\n",
    "        import numpy as np\n",
    "        return self.vec[np.random.randint(self.vec.__len__())]\n",
    "\n",
    "\n",
    "\n",
    "# Your RandomizedSet object will be instantiated and called as such:\n",
    "# obj = RandomizedSet()\n",
    "# param_1 = obj.insert(val)\n",
    "# param_2 = obj.remove(val)\n",
    "# param_3 = obj.getRandom()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberToWords(self, num: int) -> str:\n",
    "        if num == 0:\n",
    "            return 'Zero'\n",
    "        s = str(num)[::-1]\n",
    "        n = len(s)\n",
    "        #  || 9 8 7 || 6 5 4 || 3 2 1\n",
    "        kv_001 = {'1': 'One', '2': 'Two', '3': 'Three', '4': 'Four', '5': 'Five',\n",
    "                  '6': 'Six', '7': 'Seven', '8': 'Eight', '9': 'Nine'}\n",
    "        kv_001_ = {'1': 'Eleven', '2': 'Twelve', '3': 'Thirteen', '4': 'Fourteen', \n",
    "        '5': 'Fifteen', '6': 'Sixteen', '7': 'Seventeen', '8': 'Eighteen',\n",
    "        '9': 'Nineteen', '0': 'Ten'}\n",
    "        kv_010 = {'2': 'Twenty', '3': 'Thirty', '4': 'Forty', '5': 'Fifty', '6': 'Sixty',\n",
    "        '7': 'Seventy', '8': 'Eighty', '9': 'Ninety'}\n",
    "        def read(hundred, ten, one):\n",
    "            word = []\n",
    "            if hundred:\n",
    "                word.append(kv_001[hundred] + ' Hundred')\n",
    "            if ten == None:\n",
    "                if one == None:\n",
    "                    return ''\n",
    "                else:\n",
    "                    if one != '0':\n",
    "                        word.append(kv_001[one])\n",
    "            elif ten == '1':\n",
    "                word.append(kv_001_[one])\n",
    "            elif ten == '0':\n",
    "                if one and one != '0':\n",
    "                    word.append(kv_001[one])\n",
    "            else:\n",
    "                word.append(kv_010[ten])\n",
    "                if one != '0':\n",
    "                    word.append(kv_001[one])\n",
    "            return ' '.join(word)\n",
    "        res = []\n",
    "        if n > 9:\n",
    "            hundred = s[12-1] if n >= 12 else None\n",
    "            if hundred == '0': hundred = None\n",
    "            ten = s[11-1] if n >= 11 else None\n",
    "            if ten == '0' and hundred == '0': ten = None\n",
    "            one = s[10-1]\n",
    "            if one == '0' and ten == '0' and hundred == '0': one = None\n",
    "            read_result = read(hundred, ten, one)\n",
    "            if read_result:\n",
    "                res.append(read_result + ' Billion')\n",
    "        if n > 6:\n",
    "            hundred = s[9-1] if n >= 9 else None\n",
    "            if hundred == '0': hundred = None\n",
    "            ten = s[8-1] if n >= 8 else None\n",
    "            if ten == '0' and hundred == '0': ten = None\n",
    "            one = s[7-1]\n",
    "            if one == '0' and ten == '0' and hundred == '0': one = None\n",
    "            read_result = read(hundred, ten, one)\n",
    "            if read_result:\n",
    "                res.append(read_result + ' Million')\n",
    "        if n > 3:\n",
    "            hundred = s[6-1] if n >= 6 else None\n",
    "            if hundred == '0': hundred = None\n",
    "            ten = s[5-1] if n >= 5 else None\n",
    "            if ten == '0' and hundred == '0': ten = None\n",
    "            one = s[4-1]\n",
    "            if one == '0' and ten == '0' and hundred == '0': one = None\n",
    "            read_result = read(hundred, ten, one)\n",
    "            if read_result:\n",
    "                res.append(read_result + ' Thousand')\n",
    "        if n > 0:\n",
    "            hundred = s[3-1] if n >= 3 else None\n",
    "            if hundred == '0': hundred = None\n",
    "            ten = s[2-1] if n >= 2 else None\n",
    "            if ten == '0' and hundred == '0': ten = None\n",
    "            one = s[1-1]\n",
    "            if one == '0' and ten == '0' and hundred == '0': one = None\n",
    "            read_result = read(hundred, ten, one)\n",
    "            if read_result:\n",
    "                res.append(read_result)\n",
    "        return ' '.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1P3A:\n",
    "https://www.1point3acres.com/bbs/thread-1014490-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-828501-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-1014067-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-1012995-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-1006992-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-1003442-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-940767-1-1.html\n",
    "https://www.1point3acres.com/bbs/thread-933131-1-1.html\n",
    "\n",
    "LC:\n",
    "https://leetcode.cn/problems/ip-to-cidr\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Start with the initial ip address and repeat until we've covered ip + n - 1:\n",
    "        Since we want the smallest number of CIDR blocks, we want to use as large a block as possible.\n",
    "        Find the number of trailing 0s in the current ip's binary representation - let this be k.\n",
    "        The current block can cover 2^k ip addresses (with the first one being the current ip).\n",
    "        If this exceeds n, decrement k until it doesn't.\n",
    "        Add the current block to the result and move to the next ip address.\n",
    "    For easier bit manipulation, we can convert an ip address to an integer whose binary representation represents the ip address.\n",
    "    Time complexity: O(n). Space complexity: O(1) (neglecting the output list).\n",
    "    '''\n",
    "    def ipToCIDR(self, ip: str, n: int) -> list[str]:\n",
    "        # convert an ip address to an integer whose binary representation represents the ip address\n",
    "        def ipToInt(ip: str) -> int:\n",
    "            res = 0\n",
    "            for part in ip.split('.'):\n",
    "                num = int(part)\n",
    "                res = res * 256 + num\n",
    "            return res\n",
    "\n",
    "        # convert an integer whose binary representation represents an ip address to the ip address\n",
    "        def intToIp(num: int) -> str:\n",
    "            res = []\n",
    "            for _ in range(4):\n",
    "                res.append(str(num % 256))\n",
    "                num //= 256\n",
    "            return '.'.join(res[::-1])\n",
    "\n",
    "        # count the number of trailing 0s in the binary representation of an integer\n",
    "        def countTrailingZeros(num: int) -> int:\n",
    "            if num == 0: # special case\n",
    "                return 32\n",
    "\n",
    "            res = 0\n",
    "            while num & 1 == 0:\n",
    "                res += 1\n",
    "                num >>= 1\n",
    "            return res\n",
    "\n",
    "        res = []\n",
    "        ipInt = ipToInt(ip)\n",
    "        while n > 0:\n",
    "            k = countTrailingZeros(ipInt)\n",
    "            while 2 ** k > n:\n",
    "                k -= 1\n",
    "            \n",
    "            # the current CIDR block masks the last k bits of ipInt and covers 2^k ip addresses\n",
    "            res.append(intToIp(ipInt) + '/' + str(32 - k))\n",
    "            n -= 2 ** k\n",
    "            ipInt += 2 ** k\n",
    "        return res\n",
    "    \n",
    "'''\n",
    "Given a list of rules:\n",
    "[\n",
    "    (\"ALLOW\", \"1.2.3.4/32\"),\n",
    "    (\"DENY\", \"5.6.7.8/30\"),\n",
    "    ...\n",
    "]\n",
    "Determines whether an ip address is allowed or denied.\n",
    "\n",
    "Assumptions:\n",
    "    There is no contradicting rules (e.g. ALLOW and DENY rules that both apply to the ip address).\n",
    "    It's guaranteed that the ip address can match a rule.\n",
    "\n",
    "We can convert any ip address to an integer whose binary representation represents the ip address.\n",
    "For checking whether an ip address is contained in a CIDR block, \n",
    "    we can convert both addresses to integers and check whether the first k binary bits are the same by shifting.\n",
    "Time complexity: O(n). Space complexity: O(1).\n",
    "'''\n",
    "\n",
    "# convert an ip address to an integer whose binary representation represents the ip address\n",
    "def ipToInt(ip: str) -> int:\n",
    "    res = 0\n",
    "    for part in ip.split('.'):\n",
    "        num = int(part)\n",
    "        res = res * 256 + num\n",
    "    return res\n",
    "\n",
    "def isIPAllowed(rules: list[tuple[str, str]], ip: str) -> bool:\n",
    "    ipInt = ipToInt(ip)\n",
    "    for status, cidr in rules:\n",
    "        cidrIP, cidrLen = cidr.split('/')\n",
    "        cidrIPInt = ipToInt(cidrIP)\n",
    "        if ipInt >> (32 - int(cidrLen)) == cidrIPInt >> (32 - int(cidrLen)):\n",
    "            return status == 'ALLOW'\n",
    "\n",
    "'''\n",
    "What if there are many ip addresses to check?\n",
    "\n",
    "Store the rules in a hash table, with the meaningful part of the ip address as the key and the status as the value.\n",
    "For each ip address, apply each of the 31 possible masks to it and check whether the resulting ip address is in the hash table.\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], k: int) -> int:\n",
    "        # Lazy 线段树模板（区间加，查询区间最小）\n",
    "        n = len(nums)\n",
    "        mn = [0] * (4 * n)\n",
    "        todo = [0] * (4 * n)\n",
    "\n",
    "        def do(o: int, v: int) -> None:\n",
    "            mn[o] += v\n",
    "            todo[o] += v\n",
    "\n",
    "        def spread(o: int) -> None:\n",
    "            v = todo[o]\n",
    "            if v:\n",
    "                do(o * 2, v)\n",
    "                do(o * 2 + 1, v)\n",
    "                todo[o] = 0\n",
    "\n",
    "        # 区间 [L,R] 内的数都加上 v   o,l,r=1,1,n\n",
    "        def update(o: int, l: int, r: int, L: int, R: int, v: int) -> None:\n",
    "            if L <= l and r <= R:\n",
    "                do(o, v)\n",
    "                return\n",
    "            spread(o)\n",
    "            m = (l + r) // 2\n",
    "            if m >= L: update(o * 2, l, m, L, R, v)\n",
    "            if m < R: update(o * 2 + 1, m + 1, r, L, R, v)\n",
    "            mn[o] = min(mn[o * 2], mn[o * 2 + 1])\n",
    "\n",
    "        # 查询区间 [L,R] 的最小值   o,l,r=1,1,n\n",
    "        def query(o: int, l: int, r: int, L: int, R: int) -> int:\n",
    "            if L <= l and r <= R:\n",
    "                return mn[o]\n",
    "            spread(o)\n",
    "            m = (l + r) // 2\n",
    "            if m >= R: return query(o * 2, l, m, L, R)\n",
    "            if m < L: return query(o * 2 + 1, m + 1, r, L, R)\n",
    "            return min(query(o * 2, l, m, L, R), query(o * 2 + 1, m + 1, r, L, R))\n",
    "\n",
    "        ans = 0\n",
    "        last = [0] * n\n",
    "        last2 = [0] * n\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            update(1, 1, n, i, i, ans)  # 相当于设置 f[i+1] 的值\n",
    "            update(1, 1, n, last[x] + 1, i, -1)\n",
    "            if last[x]: update(1, 1, n, last2[x] + 1, last[x], 1)\n",
    "            ans = k + query(1, 1, n, 1, i)\n",
    "            last2[x] = last[x]\n",
    "            last[x] = i\n",
    "        return ans + n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        alreadylist = []\n",
    "        countlist = []\n",
    "        lent = len(s)\n",
    "        for substring in s:\n",
    "            if alreadylist.count(substring)>0:\n",
    "                continue\n",
    "            countlist.append(s.count(substring))\n",
    "            alreadylist.append(substring)\n",
    "        countlist.sort()\n",
    "        totalDelete = 0\n",
    "        gradiantList = []\n",
    "        previous = 0\n",
    "        for index in range(0,len(countlist)):\n",
    "            item = countlist[index]\n",
    "            if item>previous:\n",
    "                gradiantList.append(item)\n",
    "                previous = item\n",
    "            elif item==previous:\n",
    "                gradiantLen = len(gradiantList)\n",
    "                if previous>gradiantLen:\n",
    "                    for index in range(0,gradiantLen):\n",
    "                        lastone = gradiantList[gradiantLen-1-index]\n",
    "                        if gradiantLen-2-index >= 0:\n",
    "                            lastoneBefore = gradiantList[gradiantLen-2-index]\n",
    "                            if lastone-1>=0:\n",
    "                                gradiantList[gradiantLen-1-index] = lastone-1\n",
    "                                if lastoneBefore<lastone-1:\n",
    "                                    break\n",
    "                                else:\n",
    "                                    continue\n",
    "                        else:\n",
    "                            if gradiantLen-index >= 0 and gradiantLen-index <gradiantLen:\n",
    "                              beforeOne = gradiantList[gradiantLen-index]\n",
    "                              if lastone==beforeOne:\n",
    "                                 gradiantList[gradiantLen-1-index]=lastone-1\n",
    "                            elif index == 0 and gradiantLen == 1:\n",
    "                               gradiantList[index] = lastone-1\n",
    "                    gradiantList.append(item)\n",
    "                    for item in gradiantList:\n",
    "                        if item <= 0:\n",
    "                            gradiantList.remove(item)\n",
    "                else:\n",
    "                    #丢弃item\n",
    "                    continue \n",
    "        resultTotal = 0\n",
    "        for item in gradiantList:\n",
    "             resultTotal = resultTotal + item \n",
    "        return lent - resultTotal "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        m=n//3\n",
    "        pre=[]\n",
    "        for i in range(m):\n",
    "            pre.append(-nums[i])\n",
    "        suffix=nums[2*m:]\n",
    "        heapq.heapify(pre)\n",
    "        heapq.heapify(suffix)\n",
    "        mid=nums[m:2*m]\n",
    "        preadd=[0]*(m+1)\n",
    "        preadd[0]=-sum(pre)\n",
    "        #print(preadd)\n",
    "        #print(pre,suffix)\n",
    "        #print(mid)\n",
    "        for i in range(m):\n",
    "            if mid[i]>=-pre[0]:\n",
    "                preadd[i+1]=preadd[i]\n",
    "            else:\n",
    "                preadd[i+1]=preadd[i]+mid[i]+pre[0]\n",
    "                heapq.heappop(pre)\n",
    "                heapq.heappush(pre,-mid[i])\n",
    "        #print(preadd)\n",
    "        suffixadd=sum(suffix)\n",
    "        ans=preadd[-1]-suffixadd\n",
    "        #print(ans)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            if mid[i]<=suffix[0]:\n",
    "                continue\n",
    "            else:\n",
    "                suffixadd+=mid[i]-suffix[0]\n",
    "                heapq.heappop(suffix)\n",
    "                heapq.heappush(suffix, mid[i])\n",
    "                ans=min(ans,preadd[i]-suffixadd)\n",
    "                #print(i,preadd[i],suffix,suffixadd)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        tmp = [0] * 4\n",
    "        self.buf = []\n",
    "        num = 0\n",
    "        while num := read4(tmp):\n",
    "            for i in range(num):\n",
    "                self.buf.append(tmp[i])\n",
    "        self.p = 0\n",
    "\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        rest = len(self.buf) - self.p\n",
    "        diff = min(rest, n)\n",
    "        for i in range(diff):\n",
    "            buf[i] = self.buf[i+self.p]\n",
    "        self.p += diff\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        def reader():\n",
    "            buf4=['']*4\n",
    "            while n:=read4(buf4):\n",
    "                yield from buf4[:n]\n",
    "        self.it=reader()\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        i=-1\n",
    "        for i,c in zip(range(n),self.it):\n",
    "            buf[i]=c\n",
    "        return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Major pain point, a lot of details to consider, very boring!\n",
    "# Recite the implementation\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.buffer = [''] * 4\n",
    "        self.buffer_size = 0\n",
    "        self.buffer_pos = 0\n",
    "\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        for i in range(n):\n",
    "            if ch := self.read_char():\n",
    "                buf[i] = ch\n",
    "            else:\n",
    "                return i\n",
    "        return n\n",
    "    \n",
    "    def read_char(self):\n",
    "        if self.buffer_pos == self.buffer_size:\n",
    "            self.buffer_size = read4(self.buffer)\n",
    "            self.buffer_pos = 0\n",
    "            if self.buffer_size == 0: return None\n",
    "        result = self.buffer[self.buffer_pos]\n",
    "        self.buffer_pos += 1\n",
    "        return result\n",
    "\n",
    "    # def __init__(self):\n",
    "    #     self.pending_strs = deque()\n",
    "    #     cur_buf = [''] * 4\n",
    "    #     cur_len = read4(cur_buf)\n",
    "    #     for i in range(cur_len):\n",
    "    #         self.pending_strs.append(cur_buf[i])\n",
    "\n",
    "    # def read(self, buf: List[str], n: int) -> int:\n",
    "    #     if len(self.pending_strs) == 0: return 0\n",
    "    #     if n <= len(self.pending_strs):\n",
    "    #         for i in range(n):\n",
    "    #             buf[i] = self.pending_strs.popleft()\n",
    "    #         return n\n",
    "    #     cur_pos = 0\n",
    "    #     while self.pending_strs:\n",
    "    #         buf[cur_pos] = self.pending_strs.popleft()\n",
    "    #         cur_pos += 1\n",
    "    #     cur_buf = [''] * 4\n",
    "    #     cur_len = read4(cur_buf)\n",
    "    #     for i in range(cur_len):\n",
    "    #         self.pending_strs.append(cur_buf[i])\n",
    "    #     return cur_pos + self.read(buf, n - cur_pos)\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "    file = []\n",
    "    ptr = 0\n",
    "\n",
    "    def __init__(self):\n",
    "        buf = [None] * 4\n",
    "        read4(buf)\n",
    "\n",
    "        if buf[0]:\n",
    "            self.file = []\n",
    "            self.ptr = 0\n",
    "\n",
    "            while buf[0]:\n",
    "                self.file.extend(filter(lambda x: x, buf))\n",
    "                buf = [None] * 4\n",
    "                read4(buf)\n",
    "\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        size = 0\n",
    "        for i in range(n):\n",
    "            if self.ptr >= len(self.file):\n",
    "                break\n",
    "            # print(self.file[self.ptr])\n",
    "            buf[i] = self.file[self.ptr]\n",
    "            self.ptr += 1\n",
    "            size += 1\n",
    "        return size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.leftover = []\n",
    "\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        idx = 0\n",
    "        while n > 0:\n",
    "            buf4 = [''] * 4\n",
    "            l = read4(buf4)\n",
    "            if not l and not self.leftover:\n",
    "                break\n",
    "            \n",
    "            self.leftover.extend(buf4[:l])\n",
    "            consume = min(len(self.leftover), n)\n",
    "            buf[idx:idx + consume] = self.leftover[:consume]\n",
    "\n",
    "            idx += consume\n",
    "            n -= consume\n",
    "            self.leftover = self.leftover[consume:]\n",
    "\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# author: comiee\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        def reader():\n",
    "            buf4=['']*4\n",
    "            while n:=read4(buf4):\n",
    "                yield from buf4[:n]\n",
    "        self.it=reader()\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        i=-1\n",
    "        for i,c in zip(range(n),self.it):\n",
    "            buf[i]=c\n",
    "        return i+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.buf4 = [''] * 4\n",
    "        self.cache = []\n",
    "        self.i = 0\n",
    "\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        while self.i < n:\n",
    "            x = read4(self.buf4)\n",
    "            self.cache.extend(self.buf4[:x])\n",
    "            self.i += x\n",
    "            if x < 4:\n",
    "                break\n",
    "        m = min(self.i, n)\n",
    "        buf[:m] = self.cache[:m]\n",
    "        del self.cache[:m]\n",
    "        self.i -= m\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution: \n",
    "    def __init__(self):\n",
    "        self.seq = []\n",
    "        self.runout = False\n",
    "\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "         \n",
    "        while not self.runout and len(self.seq) < n:\n",
    "            buf4 = [None]*4\n",
    "            sz = read4(buf4)\n",
    "            self.seq += buf4[:sz] \n",
    "            if sz<4:\n",
    "                self.runout = True\n",
    "        \n",
    "        if len(self.seq) >= n : \n",
    "            for i in range(n):\n",
    "                buf[i] = self.seq[i]\n",
    "            self.seq = self.seq[n:]\n",
    "            return n\n",
    "        else: \n",
    "            sz = len(self.seq)\n",
    "            for i in range(sz):\n",
    "                buf[i] = self.seq[i]\n",
    "            self.seq = []\n",
    "            return sz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.buf = []\n",
    "\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        \n",
    "        # self.buf里面存货够用，直接取出来返回\n",
    "        if len(self.buf) >= n:\n",
    "            buf[:n] = self.buf[:n]\n",
    "            self.buf = self.buf[n:]\n",
    "            return n\n",
    "\n",
    "        # 去读取新货，直到读不到或者存货够用为止\n",
    "        idx = len(self.buf)\n",
    "        while True:\n",
    "            tmp = [None] * 4\n",
    "            m = read4(tmp)\n",
    "            if m == 0:\n",
    "                break\n",
    "            \n",
    "            self.buf += tmp[:m]\n",
    "            idx += m\n",
    "\n",
    "            if idx >= n:\n",
    "                break\n",
    "        \n",
    "        # 将存货取出来用\n",
    "        idx = min(idx, n)\n",
    "        buf[:idx] = self.buf[:idx]\n",
    "        self.buf = self.buf[idx:]\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        def reader():\n",
    "            buf4=['']*4\n",
    "            while n:=read4(buf4):\n",
    "                yield from buf4[:n]\n",
    "        self.it=reader()\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        i=-1\n",
    "        for i,c in zip(range(n),self.it):\n",
    "            buf[i]=c\n",
    "        return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.buf = []\n",
    "\n",
    "\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "\n",
    "        buf4 = [' '] * 4\n",
    "\n",
    "        n2 = n\n",
    "        wr_idx = 0\n",
    "\n",
    "        if self.buf:\n",
    "            l = len(self.buf)\n",
    "            if l > n:\n",
    "                buf[wr_idx:wr_idx+n] = self.buf[:n]\n",
    "                wr_idx += n\n",
    "                self.buf = self.buf[n:]\n",
    "                return n\n",
    "\n",
    "            else:\n",
    "                buf[wr_idx:wr_idx+l] = self.buf[:]\n",
    "                wr_idx += l\n",
    "                self.buf = []\n",
    "                n2 -= l\n",
    "\n",
    "        while True:\n",
    "            ret = read4(buf4)\n",
    "\n",
    "            if n2 < ret:\n",
    "                buf[wr_idx:wr_idx+n2] = buf4[:n2]\n",
    "                wr_idx += n2\n",
    "                self.buf.extend(buf4[n2:ret])\n",
    "                return n\n",
    "            \n",
    "\n",
    "            buf[wr_idx:wr_idx+ret] = buf4[:ret]\n",
    "            wr_idx += ret\n",
    "            n2 -= ret\n",
    "\n",
    "            if n2 == 0:\n",
    "                return n\n",
    "\n",
    "            if ret < 4:\n",
    "                return n-n2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.buf = deque([])\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        if not n:\n",
    "            return n\n",
    "        if not self.buf:\n",
    "            tmp = [''] * 4\n",
    "            length = read4(tmp)\n",
    "            if not length:\n",
    "                return 0\n",
    "            for i in range(length):\n",
    "                self.buf.append(tmp[i])\n",
    "        idx = 0\n",
    "        while self.buf:\n",
    "            buf[idx] = self.buf.popleft()\n",
    "            idx += 1\n",
    "            if idx == n:\n",
    "                return n          \n",
    "        require = n - idx\n",
    "        res = [''] * require\n",
    "        self.read(res, require)\n",
    "        for c in res:\n",
    "            buf[idx] = c\n",
    "            idx += 1\n",
    "        return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.buf = deque([])\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        if not n:\n",
    "            return n\n",
    "        if not self.buf:\n",
    "            tmp = [''] * 4\n",
    "            length = read4(tmp)\n",
    "            if not length:\n",
    "                return 0\n",
    "            for i in range(length):\n",
    "                self.buf.append(tmp[i])\n",
    "        idx = 0\n",
    "        while self.buf:\n",
    "            buf[idx] = self.buf.popleft()\n",
    "            idx += 1\n",
    "            if idx == n:\n",
    "                return n          \n",
    "        require = n - idx\n",
    "        res = [''] * require\n",
    "        self.read(res, require)\n",
    "        for c in res:\n",
    "            buf[idx] = c\n",
    "            idx += 1\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.buf = deque([])\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        if not n:\n",
    "            return n\n",
    "        if not self.buf:\n",
    "            tmp = [''] * 4\n",
    "            length = read4(tmp)\n",
    "            if not length:\n",
    "                return 0\n",
    "            for i in range(length):\n",
    "                self.buf.append(tmp[i])\n",
    "        idx = 0\n",
    "        while self.buf:\n",
    "            buf[idx] = self.buf.popleft()\n",
    "            idx += 1\n",
    "            if idx == n:\n",
    "                return n          \n",
    "        require = n - idx\n",
    "        res = [''] * require\n",
    "        self.read(res, require)\n",
    "        for c in res:\n",
    "            buf[idx] = c\n",
    "            idx += 1\n",
    "        return idx\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.buf = deque([])\n",
    "\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        if not n:\n",
    "            return n\n",
    "        if not self.buf:\n",
    "            tmp = [''] * 4\n",
    "            length = read4(tmp)\n",
    "            if not length:\n",
    "                return 0\n",
    "            for i in range(length):\n",
    "                self.buf.append(tmp[i])\n",
    "        idx = 0\n",
    "        while self.buf:\n",
    "            buf[idx] = self.buf.popleft()\n",
    "            idx += 1\n",
    "            if idx == n:\n",
    "                return n          \n",
    "        require = n - idx\n",
    "        res = [''] * require\n",
    "        self.read(res, require)\n",
    "        for c in res:\n",
    "            buf[idx] = c\n",
    "            idx += 1\n",
    "        return idx\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The read4 API is already defined for you.\n",
    "# def read4(buf4: List[str]) -> int:\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.flag=False\n",
    "        self.cnt=0\n",
    "        self.lst=[]\n",
    "    def check(self):\n",
    "        self.flag=True\n",
    "        while True:\n",
    "            tmp=[None]*4\n",
    "            cur_len=read4(tmp)\n",
    "            if cur_len==0:\n",
    "                break\n",
    "            for j in range(cur_len):\n",
    "                self.lst.append(tmp[j])\n",
    "    def read(self, buf: List[str], n: int) -> int:\n",
    "        if not self.flag:\n",
    "            self.check()\n",
    "        \n",
    "        cnt=0\n",
    "        print(self.cnt)\n",
    "        print(self.lst)\n",
    "        for _ in range(n):\n",
    "            if self.cnt<len(self.lst):\n",
    "                buf[cnt]=self.lst[self.cnt]\n",
    "                self.cnt+=1\n",
    "                cnt+=1\n",
    "        return cnt\n",
    "                \n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
